package backTrack;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class GenerateParenthesis {
    public static void main(String[] args) {
        GenerateParenthesis gp = new GenerateParenthesis();
        System.out.println(gp.generateParenthesis(3));
    }
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        char[] chars = new char[]{'(',')'};
        backtrack(res, new StringBuilder(), 0,  n,0,0);
        return res;
    }
    // 回溯算法:构建生成树形
    private void backtrack(List<String> res, StringBuilder stringBuilder, int h,  int n,int open,int close) {
        if (h == n*2) {
            // 判断括号是否合法（不是剪枝）
            if (isValidParenthsis(stringBuilder))
                res.add(String.valueOf(stringBuilder));
            return;
        }
        //剪枝（直接去除不合法的）
        if(open<n){
            stringBuilder.append('(');
            backtrack(res,stringBuilder,h+1,n,open+1,close);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
        if(close<open){
            stringBuilder.append(')');
            backtrack(res,stringBuilder,h+1,n,open,close+1);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
    }

    private static boolean isValidParenthsis(StringBuilder s) {
        if(s.length() % 2 != 0) return false;

        Stack<Character> stack = new Stack<>();

        for(int i = 0;i<s.length();i++){
            char c = s.charAt(i);
            if(c == '(') stack.push(')');
            else if(stack.isEmpty() || stack.peek() != c) return false;
            else stack.pop();
        }

        return stack.isEmpty();
    }
}
